<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.3.0">

  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.2.1/css/all.min.css" integrity="sha256-Z1K5uhUaJXA7Ll0XrZ/0JhX4lAtZFpT6jkKrEDT0drU=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">

<script class="next-config" data-name="main" type="application/json">{"hostname":"example.com","root":"/","images":"/images","scheme":"Muse","darkmode":false,"version":"8.14.1","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":{"enable":false,"style":null},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":-1,"unescape":false,"preload":false}}</script><script src="/js/config.js"></script>

    <meta name="description" content="背包问题01背包Model: 给定n个物品，第i个物品的体积为Vi,价值为Wi.背包容积为m。每件物品最多选择一次，总体积不超过m,要求总价值最大。  01背包，时间复杂度 O(nm),空间复杂度 O(nm) 1234567891011121314151617181920212223242526272829#include&lt;stdio.h&gt;#include&lt;iostream&amp;gt">
<meta property="og:type" content="article">
<meta property="og:title" content="背包问题详解">
<meta property="og:url" content="http://example.com/2021/11/10/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E8%AF%A6%E8%A7%A3/index.html">
<meta property="og:site_name" content="JsyBlog">
<meta property="og:description" content="背包问题01背包Model: 给定n个物品，第i个物品的体积为Vi,价值为Wi.背包容积为m。每件物品最多选择一次，总体积不超过m,要求总价值最大。  01背包，时间复杂度 O(nm),空间复杂度 O(nm) 1234567891011121314151617181920212223242526272829#include&lt;stdio.h&gt;#include&lt;iostream&amp;gt">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200208195835563.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQ2MzI0,size_16,color_FFFFFF,t_70">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200208205516607.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQ2MzI0,size_16,color_FFFFFF,t_70">
<meta property="article:published_time" content="2021-11-10T04:01:40.000Z">
<meta property="article:modified_time" content="2023-01-03T12:25:10.731Z">
<meta property="article:author" content="SongyangJi">
<meta property="article:tag" content="DP">
<meta property="article:tag" content="背包问题">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://img-blog.csdnimg.cn/20200208195835563.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQ2MzI0,size_16,color_FFFFFF,t_70">


<link rel="canonical" href="http://example.com/2021/11/10/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E8%AF%A6%E8%A7%A3/">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"http://example.com/2021/11/10/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E8%AF%A6%E8%A7%A3/","path":"2021/11/10/背包问题详解/","title":"背包问题详解"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>背包问题详解 | JsyBlog</title>
  








  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <div class="column">
      <header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">JsyBlog</p>
      <i class="logo-line"></i>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger" aria-label="搜索" role="button">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li><li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</header>
        
  
  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="nav-number">1.</span> <span class="nav-text">背包问题</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#01%E8%83%8C%E5%8C%85"><span class="nav-number">1.1.</span> <span class="nav-text">01背包</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%B0%8F%E6%A0%97%E5%AD%90"><span class="nav-number">1.1.1.</span> <span class="nav-text">小栗子</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85"><span class="nav-number">1.2.</span> <span class="nav-text">完全背包</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%B0%8F%E6%A0%97%E5%AD%90%E2%80%93%E8%87%AA%E7%84%B6%E6%95%B0%E6%8B%86%E5%88%86"><span class="nav-number">1.2.1.</span> <span class="nav-text">小栗子–自然数拆分</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85"><span class="nav-number">1.3.</span> <span class="nav-text">多重背包</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%9B%B4%E6%8E%A5%E6%8B%86%E5%88%86%E6%B3%95"><span class="nav-number">1.3.1.</span> <span class="nav-text">直接拆分法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BA%8C%E8%BF%9B%E5%88%B6%E6%8B%86%E5%88%86%E6%B3%95"><span class="nav-number">1.3.2.</span> <span class="nav-text">二进制拆分法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85%E6%A8%A1%E6%9D%BF%E9%A2%98"><span class="nav-number">1.3.3.</span> <span class="nav-text">多重背包模板题.</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%88%86%E7%BB%84%E8%83%8C%E5%8C%85"><span class="nav-number">1.4.</span> <span class="nav-text">分组背包</span></a></li></ol></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">SongyangJi</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">251</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">45</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">109</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>

        </div>
      </div>
    </div>

    
  </aside>


    </div>

    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://example.com/2021/11/10/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E8%AF%A6%E8%A7%A3/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="SongyangJi">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JsyBlog">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="背包问题详解 | JsyBlog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          背包问题详解
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2021-11-10 12:01:40" itemprop="dateCreated datePublished" datetime="2021-11-10T12:01:40+08:00">2021-11-10</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2023-01-03 20:25:10" itemprop="dateModified" datetime="2023-01-03T20:25:10+08:00">2023-01-03</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h1 id="背包问题"><a href="#背包问题" class="headerlink" title="背包问题"></a>背包问题</h1><h2 id="01背包"><a href="#01背包" class="headerlink" title="01背包"></a>01背包</h2><p>Model: 给定n个物品，第i个物品的体积为Vi,价值为Wi.背包容积为m。每件物品最多选择一次，总体积不超过m,要求总价值最大。</p>
<p> <strong>01背包，时间复杂度 O(nm),空间复杂度 O(nm)</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;math.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> ll long long</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn = <span class="number">1e3</span>;</span><br><span class="line"><span class="type">int</span> n,m,w[maxn],v[maxn],f[maxn][maxn];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    cin&gt;&gt;n&gt;&gt;m;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;w[i],&amp;v[i]);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>;j&lt;=m;j++) f[i][j]=f[i<span class="number">-1</span>][j];</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=v[i];j&lt;=m;j++) f[i][j] = <span class="built_in">max</span>(f[i][j],f[i<span class="number">-1</span>][j-v[i]]+w[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 打表观察</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>;j&lt;=m;j++)&#123;</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;%3d&quot;</span>,f[i][j]);</span><br><span class="line">        &#125;</span><br><span class="line">        cout&lt;&lt;endl;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><strong>状态表示</strong>：$f[i][j]$表示把 1，2，……i共 <strong>i</strong> 个物品放入容量为 <strong>j</strong> 的背包中所获得的最大价值。<br><strong>DP方程：</strong></p>
<p>$$f[i][j]&#x3D;max\begin{cases}<br>f[i-1][j]，不选第i个物品\<br>f[i-1][j-v[i]]+w[i]，if(j&gt;&#x3D;v[i]),选第i个物品<br>\end{cases}$$</p>
<p>样例<br>n&#x3D;,m&#x3D;15;<br>w[]  2 3 4 5 10<br>v[]   2 3 3 4 7<br><em>动态结果</em><br><img src="https://img-blog.csdnimg.cn/20200208195835563.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQ2MzI0,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"><br>最终答案为  f [n] [m]</p>
<p>用<strong>滚动数组</strong>进行优化<br>空间复杂度被优化为 O(m)</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> d[maxn];</span><br><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> j=m;j&gt;=<span class="number">0</span>;j--)&#123;</span><br><span class="line">        <span class="keyword">if</span>(j&gt;=v[i]) d[j]=<span class="built_in">max</span>(d[j],d[j-v[i]]+w[i]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>先使用，后更新</strong><br><strong>j</strong> 必须使用倒序循环，才保证先使用 <strong>i-1</strong> 阶段的状态，之后再更新为 <strong>i</strong> 阶段的状态，i.e. 要保证每个物品只加入一次。</p>
<h3 id="小栗子"><a href="#小栗子" class="headerlink" title="小栗子"></a>小栗子</h3><p>—<a target="_blank" rel="noopener" href="https://vjudge.net/problem/OpenJ_Bailian-4004">数字组合方案</a><br>Description：给定整数a1、a2、…an，判断是否可以从中选出若干数，使它们的和恰好为m,求方案总数。</p>
<p>状态表示：f[i][j] 前 <strong>i</strong> 个数组合得到和为 <strong>j</strong> 的方案总数<br>DP方程：$f[i][j]&#x3D;f[i-1][j]+f[i-1][j-a[i]]$<br>分别对应不取a[i]，取a[i]。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> n,m,f[<span class="number">1000</span>][<span class="number">1000</span>],a[<span class="number">1000</span>];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    cin&gt;&gt;n&gt;&gt;m;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++) &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;a[i]);</span><br><span class="line">        f[i][<span class="number">0</span>]=<span class="number">1</span>; <span class="comment">// 边界值</span></span><br><span class="line">    &#125;</span><br><span class="line">    f[<span class="number">0</span>][<span class="number">0</span>]=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>;j&lt;a[i];j++) f[i][j]= f[i<span class="number">-1</span>][j];</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=a[i];j&lt;=m;j++) f[i][j]= f[i<span class="number">-1</span>][j]+f[i<span class="number">-1</span>][j-a[i]];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 打表观察</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;=n;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>;j&lt;=m;j++)&#123;</span><br><span class="line">            cout&lt;&lt;f[i][j]&lt;&lt;<span class="string">&quot; &quot;</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        cout&lt;&lt;endl;</span><br><span class="line">    &#125;</span><br><span class="line">    cout&lt;&lt;f[n][m]&lt;&lt;endl;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<p><img src="https://img-blog.csdnimg.cn/20200208205516607.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQ2MzI0,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"><br><strong>滚动数组优化</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> n,m,f[<span class="number">10005</span>],a;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    cin&gt;&gt;n&gt;&gt;m;</span><br><span class="line">    <span class="comment">//边界值，即前i个数组合，和为0的方案数，方案数为1，也就是，前i个数都不取</span></span><br><span class="line">    f[<span class="number">0</span>]=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;a);  <span class="comment">//可以边读入边运算</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=m;j&gt;=a;j--)&#123;</span><br><span class="line">            f[j]+=f[j-a];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    cout&lt;&lt;f[m]&lt;&lt;endl;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="完全背包"><a href="#完全背包" class="headerlink" title="完全背包"></a>完全背包</h2><p>Model :  给定n个物品，第i个物品的体积为Vi,价值为Wi.背包容积为m。<strong>每件物品可以选择无数次</strong>，总体积不超过m,要求总价值最大。</p>
<p><strong>状态表示</strong>：<code>f[i][j]</code>表示把 1，2，……i共 <strong>i</strong> 个物品放入容量为 <strong>j</strong> 的背包中所获得的最大价值。<br><strong>DP方程：</strong></p>
<p>$$f[i][j]&#x3D;max\begin{cases}<br>f[i-1][j],从未选过第i种物品\<br>f[i][j-v[i]]+w[i]，if (j&gt;&#x3D;v[i]) 从第i种物品中选择一个<br>\end{cases}$$</p>
<p>在 01背包中，使用倒序循环遍历 j ,限制了每种物品最多使用一次，<br>自然，正序循环的话，每个物品就可以重复加入。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;v,&amp;w);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> j=v;j&lt;=m;j++)&#123;</span><br><span class="line">        f[j] = <span class="built_in">max</span>(f[j],f[j-v]+w);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="小栗子–自然数拆分"><a href="#小栗子–自然数拆分" class="headerlink" title="小栗子–自然数拆分"></a>小栗子–自然数拆分</h3><p>Description： 给定一个自然数N,要求把N拆分成若干个整数相加的形式，参与加法运算的数可以重复，求拆分方案。<br>思路： 1~N这N个数就是n个物品，总和 N 就是背包的容积.</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">const</span> ll mod = <span class="number">2147483648</span>;</span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line">ll f[<span class="number">4005</span>],n;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    cin&gt;&gt;n;</span><br><span class="line">    f[<span class="number">0</span>]=<span class="number">1</span>; <span class="comment">//边界值</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123; <span class="comment">//依次加入n个物品</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=i;j&lt;=n;j++)&#123; <span class="comment">//已有1~i这i个数求和得到j的方案数</span></span><br><span class="line">            f[j] = (f[j]+f[j-i])%mod;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    cout&lt;&lt;(f[n]%mod)&lt;&lt;endl;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125; </span><br></pre></td></tr></table></figure>

<h2 id="多重背包"><a href="#多重背包" class="headerlink" title="多重背包"></a>多重背包</h2><p> Model:给定n个物品，第i个物品的体积为Vi,价值为Wi.<strong>并且有Ci个</strong>,背包容积为m。总体积不超过m,要求总价值最大。</p>
<h3 id="直接拆分法"><a href="#直接拆分法" class="headerlink" title="直接拆分法"></a>直接拆分法</h3><p>把第 i 种商品看做独立的Ci个商品，相当于一共有  ${ { \sum_{ i &#x3D; 1 }^N Ci } }$个物品，就把物品转化为01背包问题了,但是效率比较低。<br>时间复杂度： $$O(M*\sum_{ i &#x3D; 1 }^N Ci)$$</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span>  f[maxn],n,m,v[maxn],w[maxn],c[maxn];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">1</span>;j&lt;=c[i];j++)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k=m;k&gt;=v[i];k--)&#123;</span><br><span class="line">                f[k] = <span class="built_in">max</span>(f[k],f[k-v[i]]+w[i]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,f[m]);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="二进制拆分法"><a href="#二进制拆分法" class="headerlink" title="二进制拆分法"></a>二进制拆分法</h3><p>把数量为Ci个的第 i 种物品拆分成 p+2种物品，它们的价值与体积分别为：<br>$$ 2^0<em>Wi,2^1</em>Wi,……2^p<em>Wi，Ri</em>Wi $$<br>$$2^0<em>Vi,2^1</em>Vi,……2^p<em>Vi，Ri</em>Vi$$<br>其中 p为满足 ${ {2^{p+1}-1&lt;&#x3D;Ci } }$ 的最大整数。<br>${ {Ri&#x3D;Ci-(2^{p+1}-1) } }$。</p>
<p>时间复杂度： $$O(M*\sum_{i&#x3D;1}^N log(Ci))$$</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">const</span> <span class="type">int</span> maxn = <span class="number">1e5</span>+<span class="number">5</span>;</span><br><span class="line"><span class="type">int</span> f[maxn],n,m,w[maxn],v[maxn],c[maxn];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">while</span> (<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;m,&amp;n)==<span class="number">2</span>) &#123;</span><br><span class="line">        <span class="built_in">memset</span>(f, <span class="number">0</span>, <span class="built_in">sizeof</span>(f));</span><br><span class="line">        <span class="built_in">memset</span>(w, <span class="number">0</span>, <span class="built_in">sizeof</span>(w));</span><br><span class="line">        <span class="built_in">memset</span>(c, <span class="number">0</span>, <span class="built_in">sizeof</span>(c));</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;c[i],&amp;w[i]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">            <span class="type">int</span> p = (<span class="type">int</span>)<span class="built_in">log2</span>(c[i]+<span class="number">1</span>)<span class="number">-1</span>;</span><br><span class="line">            <span class="type">int</span> ri= -<span class="built_in">pow</span>(<span class="number">2</span>, p+<span class="number">1</span>)+c[i]+<span class="number">1</span>;</span><br><span class="line">            <span class="type">int</span> wp[p+<span class="number">5</span>],vp[p+<span class="number">5</span>];</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> x=<span class="number">0</span>;x&lt;=p;x++)&#123;</span><br><span class="line">                wp[x]=<span class="built_in">pow</span>(<span class="number">2</span>,x)*w[i];</span><br><span class="line">                vp[x]=<span class="built_in">pow</span>(<span class="number">2</span>,x)*v[i]</span><br><span class="line">            &#125;</span><br><span class="line">            wp[p+<span class="number">1</span>]=ri*w[i];v[p+<span class="number">1</span>]=ri*v[i];</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>;j&lt;=p+<span class="number">1</span>;j++)&#123;</span><br><span class="line">                <span class="keyword">for</span>(<span class="type">int</span> k=m;k&gt;=vp[j];k--)&#123;</span><br><span class="line">                    f[k] = <span class="built_in">max</span>(f[k],f[k-vp[j]]+wp[j]);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,f[m]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="多重背包模板题"><a href="#多重背包模板题" class="headerlink" title="多重背包模板题."></a><a target="_blank" rel="noopener" href="https://vjudge.net/problem/UVA-10626">多重背包模板题</a>.</h3><h2 id="分组背包"><a href="#分组背包" class="headerlink" title="分组背包"></a>分组背包</h2><p> Model : 给定 <strong>N</strong> 组物品，其中第 <strong>i</strong> 组有 <strong>Ci</strong> 个物品。第 i 组的第 <strong>j</strong> 个物品的体积为 <strong>Vij</strong>,价值为 <strong>Wij</strong>。有一个容积为 M 的背包，使得<strong>每组至多选择一个物品</strong>并且总体积不超过M的前提下，物品的价值和最大。<br><strong>状态</strong>:$F[i][j]$,表示从前 <strong>i</strong> 组中选出总体积为 <strong>j</strong> 的物品放入背包，物品的最大价值和。<br><strong>DP方程</strong>：<br>$$f[i][j]&#x3D;max\begin{cases}<br>f[i-1][j]，不选第 i 组物品\<br>max_{(1&#x3D;&lt;k&lt;&#x3D;C_i)}f[i-1][j-V_{ik}]+W_{ik}，选第i组物品的某个物品k<br>\end{cases}$$</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> j=m;j&gt;=<span class="number">0</span>;j--)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> k=<span class="number">1</span>;k&lt;=c[i];k++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(j&gt;=v[i][k])</span><br><span class="line">                f[j]=<span class="built_in">max</span>(f[j],f[j-v[i][k]]+w[i][k]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,f[m]);</span><br></pre></td></tr></table></figure>
<p>注意点：<strong>倒序循环j</strong>;<br><strong>对每一组物品的循环k应该放在j的内层，以保证每个物品只会放进去一次。</strong><br>从动态规划的角度：<br><strong>i</strong>是”阶段“，<strong>i</strong>和<strong>j</strong>共同构成”状态“，而<strong>k</strong>是”决策“——在第<strong>i</strong>个阶段使用哪个物品。</p>

    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/DP/" rel="tag"># DP</a>
              <a href="/tags/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/" rel="tag"># 背包问题</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2021/11/03/MySQL%E7%B3%BB%E5%88%97%E2%80%94%E2%80%94-%E9%94%81%E6%9C%BA%E5%88%B6/" rel="prev" title="MySQL系列 —— 锁机制">
                  <i class="fa fa-chevron-left"></i> MySQL系列 —— 锁机制
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/2021/11/11/%E5%A4%A7%E6%95%B4%E6%95%B0%E5%8F%96%E6%A8%A1%E3%80%81%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0%E4%B8%8E%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0%E3%80%81%E5%BF%AB%E9%80%9F%E5%B9%82%E4%B8%8E%E6%85%A2%E9%80%9F%E4%B9%98/" rel="next" title="大整数取模、最大公约数与最小公倍数、快速幂与慢速乘、矩阵乘法加速">
                  大整数取模、最大公约数与最小公倍数、快速幂与慢速乘、矩阵乘法加速 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 
  <span itemprop="copyrightYear">2023</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">SongyangJi</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/muse/" rel="noopener" target="_blank">NexT.Muse</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>
  <div class="sidebar-dimmer"></div>
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up fa-lg"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


  
  <script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script>

  <script src="https://cdnjs.cloudflare.com/ajax/libs/hexo-generator-searchdb/1.4.1/search.js" integrity="sha256-1kfA5uHPf65M5cphT2dvymhkuyHPQp5A53EGZOnOLmc=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>





  





</body>
</html>
